package huawei.year2016;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Scanner;

/**
 * Created by Hyman on 2017/3/16.
 * <p>
 * 数独是一个我们都非常熟悉的经典游戏，运用计算机我们可以很快地解开数独难题，现在有一些简单的数独题目，请编写一个程序求解。
 * 这里的数独就是9行9列的数组，满足每一行、每一列、每一个3*3粗线宫内的数字均含1-9，不重复。
 * <p>
 * 输入描述: 输入9行，每行为空格隔开的9个数字，为0的地方就是需要填充的。
 * 输出描述: 输出九行，每行九个空格隔开的数字，为解出的答案
 */
public class Sudoku {


    public static void main(String[] args) {

        //Scanner scanner = new Scanner(System.in);
        Scanner scanner = new Scanner(Sudoku.class.getClassLoader().getResourceAsStream("huawei/year2016/data.txt"));

        while (scanner.hasNext()) {

            int[][] sudoku = new int[9][9];

            List<HashSet<Integer>> rows = new ArrayList<>();
            List<HashSet<Integer>> cols = new ArrayList<>();
            List<HashSet<Integer>> blocks = new ArrayList<>();

            for (int k = 0; k < 9; k++) {
                rows.add(new HashSet<Integer>());
                cols.add(new HashSet<Integer>());
                blocks.add(new HashSet<Integer>());
            }

            for (int i = 0; i < 9; i++) {

                for (int j = 0; j < 9; j++) {

                    sudoku[i][j] = scanner.nextInt();

                    if(sudoku[i][j] != 0) {
                        rows.get(i).add(sudoku[i][j]);
                        cols.get(j).add(sudoku[i][j]);
                        blocks.get(i / 3 * 3 + j / 3).add(sudoku[i][j]);
                    }
                }
            }

            dfs(sudoku, rows, cols, blocks, 0);

            System.out.println(ArrToString(sudoku));
        }

        scanner.close();
    }

    private static boolean dfs(int[][] sudoku, List<HashSet<Integer>> rows, List<HashSet<Integer>> cols, List<HashSet<Integer>> blocks, int index) {

        if (index == 81) {
            return true;
        }

        int m = index / 9;
        int n = index % 9;
        int l = m / 3 * 3 + n / 3; //第几个3*3方块,总共0-8个

        if (sudoku[m][n] != 0) {

            return dfs(sudoku, rows, cols, blocks, index + 1);

        } else {

            for (int i = 1; i <= 9; i++) {

                if (!rows.get(m).contains(i) && !cols.get(n).contains(i) && !blocks.get(l).contains(i)) {

                    sudoku[m][n] = i;
                    rows.get(m).add(i);
                    cols.get(n).add(i);
                    blocks.get(l).add(i);

                    if (dfs(sudoku, rows, cols, blocks, index + 1)) {
                        return true;
                    }

                    sudoku[m][n] = 0;
                    rows.get(m).remove(i);
                    cols.get(n).remove(i);
                    blocks.get(l).remove(i);
                }
            }

            return false;
        }
    }


    private static String ArrToString(int[][] sudoku) {

        StringBuilder sb = new StringBuilder();

        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                sb.append(sudoku[i][j] + " ");
            }
            sb.setCharAt(sb.length() - 1, '\n');
        }
        return sb.substring(0, sb.length() - 1);
    }
}
